public class L28 {
    public static void main(String[] args) {
        String haystack = "aadaadaaf";
        String needle = "aadaaf";
        int i = new Solution().strStr(haystack, needle);
        System.out.println(i);
    }

    static class Solution {
        //        kmp算法
        public int strStr(String haystack, String needle) {
            char[] chars = needle.toCharArray();
            int[] next = new int[chars.length];
            getNext(next, chars);

            char[] source = haystack.toCharArray();
            int j = 0;
            for (int i = 0; i < source.length; i++) {
                while (j > 0 && chars[j] != source[i]) {
                    j = next[j - 1];
                }
                if (chars[j] == source[i]) {
                    j++;
                }
                if (j == chars.length) {
                    return i - chars.length + 1;
                }
            }

            return -1;

        }

        private void getNext(int[] next, char[] chars) {
            int i = 0;
            next[i] = 0;
            for (int j = 1; j < chars.length; j++) {
                while (i > 0 && chars[i] != chars[j]) {
                    i = next[i - 1];
                }
                if (chars[i] == chars[j]) {
                    i++;
                }
                next[j] = i;
            }
        }
    }


//    static class Solution {
//        public int strStr(String haystack, String needle) {
//            char[] chars = haystack.toCharArray();
//            int index = 0;
//            while (index < chars.length) {
//                int i = 1;
//                if (chars[index] == needle.charAt(0)) {
//                    while (i < needle.length() && index + i < chars.length && chars[index + i] == needle.charAt(i)) {
//                        i++;
//                    }
//                    if (i == needle.length()) {
//                        return index;
//                    }
////                    i--;
//                }
//                index++;
//
//            }
//            return -1;
//
//        }
//    }
}
